package leetcode.code0786;

import java.util.PriorityQueue;

import leetcode.helper.MaxDebug;

public class Solution extends Solution786 {

	@Override
	public int[] kthSmallestPrimeFraction(int[] arr, int k) {
		PriorityQueue<int[]> p = new PriorityQueue<>((a, b) -> {
			if (b[0] * 1.0 / b[1] - a[0] * 1.0 / a[1] > 0)
				return 1;
			else
				return -1;
		});
		int LEN = arr.length;
		for (int i = 0; i < LEN; i++) {
			for (int j = LEN - 1; j >= 0; j--) {
				if (p.size() == k) {
					int[] top = p.peek();
					if (top[0] * 1.0 / top[1] > arr[i] * 1.0 / arr[j]) {
						p.poll();
						p.add(new int[] { arr[i], arr[j] });
					}
				} else {
					p.add(new int[] { arr[i], arr[j] });
				}
			}
		}
		return p.poll();
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		MaxDebug.debug14(so);
	}

}
